package data_structures_and_algorithms.recursion_traceback;

import java.util.Arrays;

/**
 * @ClassName _38PermutationString
 * @Description: 输入一个字符串，打印出该字符串中字符的所有排列。
 *
 *  
 *
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 *
 *  
 *
 * 示例:
 *
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 *  
 *
 * 限制：
 *
 * 1 <= s 的长度 <= 8
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/13 10:25
 */
public class _38PermutationString {

    private int resultIndex = 0;

    public static void main(String[] args) {
        String s = "abcd";
        String[] permutationImprove = new _38PermutationString().new PermutationImprove().permutation(s);
        System.out.println(Arrays.toString(permutationImprove));
    }

    public class PermutationImprove{
        // 回溯：转换为数组，然后交换字符位置输出最终的字符串
        public String[] permutation(String s) {
            int size = 1;
            char[] chars = new char[s.length()];
            for (int i = 0; i < s.length(); i++) {
                size *= (i + 1);
                chars[i] = s.charAt(i);
            }
            String[] result = new String[size];
            StringBuilder sb = new StringBuilder();
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                swap(chars, i, index);
                sb.append(chars[index]);
                traceback(chars, index + 1, result, sb);
                // 回溯
                sb.deleteCharAt(index);
                swap(chars, i, index);
            }

            return result;
        }

        public void traceback(char[] chars, int index, String[] result, StringBuilder sb){
            if (index == chars.length){
                result[resultIndex++] = sb.toString();
                return;
            }

            for (int i = index; i < chars.length; i++) {
                swap(chars, i, index);
                sb.append(chars[index]);
                traceback(chars, index + 1, result, sb);
                sb.deleteCharAt(index);
                swap(chars, i, index);
            }
        }
    }

    public void swap(char[] chars, int a, int b){
        char temp = chars[a];
        chars[a] = chars[b];
        chars[b] = temp;
    }

}
